package com.shm.leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * 897. 递增顺序搜索树
 * 给你一棵二叉搜索树，请你 按中序遍历 将其重新排列为一棵递增顺序搜索树，使树中最左边的节点成为树的根节点，并且每个节点没有左子节点，只有一个右子节点。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：root = [5,3,6,2,4,null,8,1,null,null,null,7,9]
 * 输出：[1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]
 * 示例 2：
 *
 *
 * 输入：root = [5,1,7]
 * 输出：[1,null,5,null,7]
 *
 *
 * 提示：
 *
 * 树中节点数的取值范围是 [1, 100]
 * 0 <= Node.val <= 1000
 * @author SHM
 */
public class IncreasingBST {
    List<TreeNode> list = new ArrayList<>();

    /**
     * 方法一：中序遍历之后生成新的树
     * 算法
     *
     * 题目要求我们返回按照中序遍历的结果改造而成的、只有右节点的等价二叉搜索树。我们可以进行如下操作：
     *
     * 先对输入的二叉搜索树执行中序遍历，将结果保存到一个列表中；
     *
     * 然后根据列表中的节点值，创建等价的只含有右节点的二叉搜索树，其过程等价于根据节点值创建一个链表。
     *
     * 复杂度分析
     *
     * 时间复杂度：O(n)O(n)，其中 nn 是二叉搜索树的节点总数。
     *
     * 空间复杂度：O(n)O(n)，其中 nn 是二叉搜索树的节点总数。需要长度为 nn 的列表保存二叉搜索树的所有节点的值。
     *
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/increasing-order-search-tree/solution/di-zeng-shun-xu-cha-zhao-shu-by-leetcode-dfrr/
     * @param root
     * @return
     */
    public TreeNode increasingBST(TreeNode root) {
        middleOrder(root,list);
        TreeNode head = new TreeNode();
        int size = list.size();
        if (size>0){
            head.val = list.get(0).val;
        }
        TreeNode node = head;
        for (int i = 1; i < size; i++) {
            node.right = new TreeNode(list.get(i).val);
            node = node.right;
        }
        node.right = null;
        return head;
    }

    void middleOrder(TreeNode root,List<TreeNode> list){
        if (root==null){
            return;
        }
        middleOrder(root.left,list);
        list.add(root);
        middleOrder(root.right,list);
    }

    TreeNode node;

    /**
     * 方法二：在中序遍历的过程中改变节点指向
     * 算法
     *
     * 方法一需要遍历一次二叉搜索树以后，然后再创建新的等价的二叉搜索树。事实上，还可以遍历一次输入二叉搜索树，在遍历的过程中改变节点指向以满足题目的要求。
     *
     * 在中序遍历的时候，修改节点指向就可以实现。具体地，当我们遍历到一个节点时，把它的左孩子设为空，并将其本身作为上一个遍历到的节点的右孩子。这里需要有一些想象能力。递归遍历的过程中，由于递归函数的调用栈保存了节点的引用，因此上述操作可以实现。下面的幻灯片展示了这样的过程。
     *
     * 复杂度分析
     *
     * 时间复杂度：O(n)O(n)，其中 nn 是二叉搜索树的节点总数。
     *
     * 空间复杂度：O(n)O(n)。递归过程中的栈空间开销为 O(n)O(n)。
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/increasing-order-search-tree/solution/di-zeng-shun-xu-cha-zhao-shu-by-leetcode-dfrr/
     * @param root
     * @return
     */
    public TreeNode increasingBST_2(TreeNode root) {
        TreeNode dummyNode = new TreeNode(-1);
        node = dummyNode;
        inOrder(root);
        return dummyNode.right;
    }

    void inOrder(TreeNode root){
        if (root==null){
            return;
        }
        inOrder(root.left);
        // 在中序遍历的过程中修改节点指向
        node.right = root;
        node.left = null;
        node = root;
        inOrder(root.right);
    }
}
